package com.test.ds.sort.quicksort;

public class ArrayIns {
	private long[] theArray;
	private int nElems;
	
	public ArrayIns(int max){
		theArray = new long[max];
		nElems = 0;
	}
	
	public void insert(long value){
		theArray[nElems] = value;
		nElems++;
	}
	
	public int size(){
		return nElems;
	}
	
	public void display(){
		System.out.print("A = ");
		for(int j=0; j<nElems; j++){
			System.out.print(theArray[j] + " ");
		}
		System.out.println("");
	}
	
	public void quickSort() {
		recQuickSort(0, nElems-1);
		
	}

	private void recQuickSort(int left, int right) {
		int size = right-left+1;
		if( size <= 3){
			manualSort(left, right);
		}else{
			long median = medianof3(left, right);
			
			int partition = partitionIt(left, right, median);
			recQuickSort(left, partition-1);
			recQuickSort(partition+1, right);
		}
		
	}
	
	private long medianof3(int left, int right) {
		// TODO Auto-generated method stub
		return 0;
	}

	private void manualSort(int left, int right) {
		// TODO Auto-generated method stub
		
	}

	public int partitionIt(int left, int right, long pivot){
		int leftPtr = left - 1;
		int rightPtr = right;
		
		while(true){
			while(theArray[++leftPtr] < pivot){
				;
			}
			
			while(rightPtr > 0 && theArray[--rightPtr] > pivot){
				;
			}
			
			if(leftPtr >= rightPtr){
				break;
			}else{
				swap(leftPtr, rightPtr);
			}
		}
		swap(leftPtr, right);
		return leftPtr;
	}

	private void swap(int dex1, int dex2) {
		long temp;
		temp = theArray[dex1];
		theArray[dex1] = theArray[dex2];
		theArray[dex2] = temp;
		
	}



}
